[BAEKJOON] 4577. 소코반

Posted on June 25, 2021

문제 :

소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수는 같다. 플레이어는 화살표(위, 아래, 왼쪽, 오른쪽)를 이용해 캐릭터를 아래와 같은 규칙으로 조정할 수 있다.

캐릭터에게 지시한 방향이 빈 칸(박스나 벽이 아닌 곳)인 경우에는 그 칸으로 이동한다.
지시한 방향에 박스가 있는 경우에는, 박스를 민다. 이 경우에는 박스가 이동할 칸도 비어있어야 한다.
지시한 방향이 벽인 경우, 또는 박스가 있는데, 박스가 이동할 칸에 다른 박스나 벽이 있는 경우에는 키를 눌러도 캐릭터는 이동하지 않는다.

모든 박스를 목표점으로 이동시킨 경우에 게임은 끝난다. 게임이 끝난 후에 입력하는 키는 모두 무시된다.

준규는 소코반으로 고통받는 친구들을 위해서 소코반의 해를 찾는 프로그램을 작성하려고 한다. 하지만, 소코반의 해를 찾는 문제는 NP-hard와 PSPACE-complete에 속하고, 매우 어려운 문제이다. 따라서, 간단한 소코반 프로그램을 작성해보려고 한다.

사용자가 입력한 키가 순서대로 주어졌을 때, 게임이 어떻게 진행되는지를 구하는 프로그램을 작성하시오.

게임의 상태는 아래와 같은 문자로 나타낼 수 있다.

문자	뜻
.	빈 공간
#	벽
+	비어 있는 목표점
b	박스
B	목표점 위에 있는 박스
w	캐릭터
W	목표점 위에 있는 캐릭터

첫 번째 입력은 문제의 그림과 같다.

입력 :

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 행과 열의 수 R, C가 주어진다. (4 ≤ R ≤ 15, 4 ≤ C ≤ 15) 다음 R개 줄에는 현재 게임의 상태가 주어진다. 모든 줄은 C개의 문자로 이루어져 있다. 마지막 줄에는 플레이어가 입력한 키가 순서대로 주어지며 길이는 최대 50이다. 위, 아래, 왼쪽, 오른쪽은 U, D, L, R로 나타낸다.

입력의 마지막 줄에는 0 0이 주어진다.

입력으로 주어지는 모든 데이터는 항상 캐릭터가 한 명이고, 박스의 수와 목표점의 수는 같다. 또, 목표점 위에 올라가 있지 않은 박스는 적어도 한 개 이며, 가장 바깥쪽 칸은 항상 벽이다.

출력 :

각각의 게임에 대해서, 게임 번호를 출력한 다음에 게임이 끝났으면 complete를, 아니면 incomplete를 출력한다. 그 다음 줄부터 R개 줄에는 게임의 상태를 출력한다.

풀이 :

소코반 게임의 최소 이동횟수를 구하는 문제가 아니고, 이동방향을 가리키는 문자열을 보고 해당 이동으로 게임을 해결할 수 있는지 없는지에 관한 문제로 구현 카테고리의 문제였다.

박스가 목표점에 도달해도 다시 벗어날 수 있으며, 유저가 목표점에 서있을 수 있거나 박스가 벽이나 박스로 가로막힌 경우 등의 여러 변수 상황들만 잘 캐치한다면 구현은 크게 어렵지 않은 문제였다.

[ 주의사항 ]

유저가 이동한 방향 뿐만 아니라 전에 있던 위치를 잘 업데이트 해주는 것도 중요하다. 전의 위치를 업데이트 해주는 것은 크게 두 가지 분류가 있다. 유저가 목표점에 서 있는 경우, 서 있지 않은 경우. 목표점에 서 있는 경우에는 유저가 이동하고 난 후 기존의 위치에 ’+’ 문자를 넣어주어야 한다. 이 외의 경우에는 ’.’ 문자를 넣어준다.
처음에는 이동방향을 가리키는 문자열을 보고 첨부터 끝까지 이동시켜준 후 게임 complete 여부를 따져주었다. 하지만 문제를 잘 읽어보면 이동방향 문자열 중간에 박스를 모두 목표점에 이동시킨 경우에는 해당 지점에서 게임을 종료하고 결과값을 출력해주면 된다. 따라서 매 이동 순간마다 목표점에 다다르지 못한 박스의 갯수를 세고 있어야 한다.

[ 세부 구현사항 ]

map을 입력받음과 동시에 유저의 위치와 목표점에 도달하지 못한 ‘b’의 갯수를 확인한다.
입력받은 이동 방향 문자열을 첨부터 차례로 이동시켜나가면서 벽일 경우, 목표점일 경우, 박스일 경우, 빈 공간일 경우에 대해 세부적으로 케이스를 만들어 모든 경우의 수 조건문을 세세하게 구현한다.
이동 방향 진행 중 모든 박스가 목표점에 다다르면 곧바로 게임을 종료시킨다.

코드 :

코드 보기/접기

#include <iostream>
#include <string>

using namespace std;
int rows, cols, di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
char map[15][15];

int changeDirNumber(char ch) {
    switch (ch) {
        case 'R':
            return 0;
        case 'D':
            return 1;
        case 'L':
            return 2;
        case 'U':
            return 3;
    }
}

void testCase(int casenum) {
    int curx, cury, remains = 0;
    bool iscomplete = true;
    string movestr;

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'w' || map[i][j] == 'W') {
                curx = i;
                cury = j;
            } else if (map[i][j] == 'b') remains++;
        }

    cin >> movestr;
    int length = movestr.length();

    for (int k = 0; k < length; k++) {
        int curdir = changeDirNumber(movestr[k]), cmpx = curx + di[curdir], cmpy = cury + dj[curdir];
        char cmpch = map[cmpx][cmpy];

        if (cmpch == '#') continue;
        if (cmpch == '+') map[cmpx][cmpy] = 'W';
        else if (cmpch == '.') map[cmpx][cmpy] = 'w';
        else if (cmpch == 'b' || cmpch == 'B') {
            int nextx = cmpx + di[curdir], nexty = cmpy + dj[curdir];
            char nextch = map[nextx][nexty], flagch = (cmpch == 'b') ? 'w' : 'W';

            if (nextch == '+') {
                map[nextx][nexty] = 'B';
                map[cmpx][cmpy] = flagch;
                if (flagch == 'W') remains++;
                remains--;
            } else if (nextch == '.') {
                map[nextx][nexty] = 'b';
                map[cmpx][cmpy] = flagch;
                if (flagch == 'W') remains++;
            } else continue;
        }

        if (map[curx][cury] == 'W') map[curx][cury] = '+';
        else map[curx][cury] = '.';
        // 기존의 자리 문자 교체

        if (!remains) break;

        curx = cmpx;
        cury = cmpy;
    }

    cout << "Game " << casenum << ": " << (remains ? "incomplete\n" : "complete\n");

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++)
            cout << map[i][j];
        cout << '\n';
    }
}

int main() {
    int cnt = 1;

    while (true) {
        cin >> rows >> cols;
        if (!rows && !cols) break;
        testCase(cnt++);
    }

    return 0;
}

Algorithm

algorithm baekjoon C++